#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class maxBinaryTree {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size());
    }

    TreeNode* build(vector<int>& nums, int left, int right) {
        if (left >= right)
            return nullptr;

        int maxValue = INT_MIN;
        int maxIndex = 0;
        for (int i = left; i < right; i++) {
            if (nums[i] > maxValue) {
                maxIndex = i;
                maxValue = nums[i];
            }
        }

        TreeNode *root = new TreeNode(maxValue);
        root->left = build(nums, left, maxIndex);
        root->right = build(nums, maxIndex + 1, right);

        return root;
    }
};

class buildTreeByPreorderAndInorder {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++)
            valToIndex[inorder[i]] = i;
        tag = 0;
        return build(preorder, inorder, 0, preorder.size());
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int left, int right) {
        if (left >= right)
            return nullptr;
        
        TreeNode* root = nullptr;

        int pos = valToIndex[preorder[tag]];
        root = new TreeNode(preorder[tag++]);
        root->left = build(preorder, inorder, left, pos);
        root->right = build(preorder, inorder, pos + 1, right);

        return root;
    }
private:
    unordered_map<int, int> valToIndex;
    int tag;
};

class buildTreeByPostorderAndInorder {
public:
    TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++)
            valToIndex[inorder[i]] = i;
        tag = inorder.size();
        return build(postorder, inorder, 0, inorder.size());
    }

    TreeNode* build(vector<int>& postorder, vector<int>& inorder, int left, int right) {
        if (left >= right)
            return nullptr;
        
        TreeNode* root = nullptr;

        int pos = valToIndex[postorder[tag]];
        root = new TreeNode(postorder[tag--]);
        root->right = build(postorder, inorder, pos + 1, right);
        root->left = build(postorder, inorder, left, pos);

        return root;
    }
private:
    unordered_map<int, int> valToIndex;
    int tag;
};